#ifndef QUAD_TREE_HPP
#define QUAD_TREE_HPP

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <unordered_set>

#include <SFML/Graphics/Color.hpp>

#include <SmegTools/Config.h>

#include "../../Entity/BaseObject.hpp"
#include "../BoundingVolumes/BoundingVolume.hpp"

#ifdef _DEBUG
namespace sf {
    class RenderWindow;
}
#endif

#include <SmegTools/Debug/DebugNew.hpp>

namespace smeg {
    namespace math {

class BoundingBox;
class QuadTreeNode;

////////////////////////////////////////////////////////////
/// Represents a QuadTree
////////////////////////////////////////////////////////////
class QuadTree
{
    typedef    std::unordered_set< core::BaseObject* >                        td_OccupantsSet;
    typedef    std::unordered_set< core::BaseObject* >::iterator              td_OccupantsSetIt;
    typedef    std::unordered_set< core::BaseObject* >::const_iterator        td_OccupantsSetConstIt;

    ////////////////////////////////////////////////////////////
    /// Copy Constructor
    ////////////////////////////////////////////////////////////
    QuadTree( const QuadTree& _Copy ) {}

public:
    ////////////////////////////////////////////////////////////
    /// Default Constructor
    ///
    ////////////////////////////////////////////////////////////
                    QuadTree();
    ////////////////////////////////////////////////////////////
    /// Constructor
    ///
    /// \param _Region : Region this tree represents
    ///
    ////////////////////////////////////////////////////////////
                    QuadTree( const math::BoundingBox& _Region );
    ////////////////////////////////////////////////////////////
    /// Destructor
    ///
    ////////////////////////////////////////////////////////////
    virtual         ~QuadTree();
    
    ////////////////////////////////////////////////////////////
    /// Create the tree
    ///
    /// \param _region : Region this tree represents
    ///
    ////////////////////////////////////////////////////////////
    void            Create( const math::BoundingBox& _Region );
    ////////////////////////////////////////////////////////////
    /// Clear the tree
    ///
    ////////////////////////////////////////////////////////////
    void            Clear();
    
    ////////////////////////////////////////////////////////////
    /// Add an occupant to the tree
    ///
    /// \param _pNewOccupant :      Occupant to add
    ///
    ////////////////////////////////////////////////////////////
    void            Add( core::BaseObject* _pOccupant );
    ////////////////////////////////////////////////////////////
    /// Add an occupant outside the tree
    ///
    /// \param _pNewOccupant :      Occupant to add
    ///
    ////////////////////////////////////////////////////////////
    void            AddOutside( core::BaseObject* _pOccupant );
    ////////////////////////////////////////////////////////////
    /// Update the occupation of this tree with the given occupant
    /// This function check the occupant's containment, it either :
    ///     - update the occupant's node
    ///     - if the occupant was outside add the occupant normally
    ///
    /// \param _pNewOccupant :      Occupant to update
    ///
    ////////////////////////////////////////////////////////////
    void            Update( core::BaseObject* _pOccupant );
    ////////////////////////////////////////////////////////////
    /// Remove an occupant from this tree
    ///
    /// \param _pNewOccupant :      Occupant to remove
    ///
    ////////////////////////////////////////////////////////////
    void            Remove( core::BaseObject* _pOccupant );
    
    ////////////////////////////////////////////////////////////
    /// Query a region and retrieve the occupants in this region
    ///
    /// \param _Region :            Region to check
    /// \param _Result :            Output vector of occupants
    ///
    ////////////////////////////////////////////////////////////
    void            QueryRegion( const math::BoundingBox& _Region, std::vector<core::BaseObject*>& _Result, BoundingVolume::eBoundingVolume _eType = BoundingVolume::eAny ) const;
    
    ////////////////////////////////////////////////////////////
    /// Is the tree created or not ?
    ///
    /// \return Whether the tree was created or not
    ///
    ////////////////////////////////////////////////////////////
    bool            IsCreated() const;

private:
    /********************* Private members ********************/
    QuadTreeNode*   m_pRoot;                /// Root node
    td_OccupantsSet m_OutsideOccupants;     /// Outside occupants
    
#ifdef _DEBUG
public:
    void            DebugRender( sf::RenderWindow* _pRenderWindow ) const;
#endif // _DEBUG
};

/************************** Inline ************************/

////////////////////////////////////////////////////////////
/// Is the tree created or not ?
////////////////////////////////////////////////////////////
inline bool QuadTree::IsCreated() const {
    return ( m_pRoot != NULL );
}

    } // namespace light
} // namespace smeg

#include <SmegTools/Debug/DebugNewOff.hpp>

#endif // QUAD_TREE_HPP
